package me.yobol.lintcode.easy.pluswithbit;

/**
 * 
 * 
 *
 * @author Yobol
 */
public class PlusWithBit implements IPlusWithBit{
    
    /**
     * a + b
     * 00 + 00 = 00
     * 00 + 01 = 01
     * 01 + 00 = 01
     * 01 + 01 = 10
     * 
     * a ^ b是不完全加法，每次都忽略了进位
     * 00 ^ 00 = 00
     * 00 ^ 01 = 01
     * 01 ^ 00 = 01
     * 01 ^ 01 = 00
     * 
     * 而(a & b ) << 1恰好能计算进位
     * 00 & 00 << 1 = 0
     * 00 & 01 << 1 = 0
     * 01 & 00 << 1 = 0
     * 01 & 01 << 1 = 1
     * 
     * 如1 + 1 = (01 ^ 01) ^ ((01 & 01) << 1)
     * 
     * 首先a & b计算好进位的数字，
     * 然后a ^ b不完全加法一次，
     * 然后b用来放剩下的carry，每次移动一位，继续加，直到b为0为止
     * @param a
     * @param b
     * @return 
     */
    public int plusWithBit(int a,int b){
        int carry;
        while (b != 0) {
            carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}
